/*
 *  分考场 dfs 2017 国赛
 * */

#include <iostream>

using namespace std;

const int N = 105;
int n, m;
bool g[N][N];
int r[N][N];
int res = 0x3f;

void dfs(int no, int rm) {
    if (rm >= res) {
        return;
    }
    if (no > n) {
        res = rm;
    } else {
        for (int i = 1; i <= rm; ++i) {
            int k = 0;
            while (r[i][k] && g[no][r[i][k]] == 0) {
                ++k;
            }
            if (!r[i][k]) {
                r[i][k] = no;
                dfs(no + 1, rm);
                r[i][k] = 0;
            }
        }

        r[rm + 1][0] = no;
        dfs(no + 1, rm + 1);
        r[rm + 1][0] = 0;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        g[a][b] = true, g[b][a] = true;
    }

    dfs(1, 1);
    cout << res << '\n';
    return 0;
}